# -*- coding: utf-8 -*-

'''
@author: Luis Fonte n6043
@date: 10/06/2013
@obs: Code created on class from documentation given by teacher
'''

import sys
import math


class MergeAlgorithm():
    '''
    Class MergeAlgorithm
    Class with a merge sort algorithm implemented on function merge_sort
    '''

    def __init__(self, A):
        '''
        Class Constructor
        @param A - list with numbers desordered
        '''
        self.A = A
        self.p = 0
        self.r = len(self.A)-1
        pass

    
    def merge(self, A, p, q, r):
        '''
        function merge
        Adds two sub sequences ordered
        @param A - list of numbers
        @param p - index of A (first value)
        @param q - index of A (middle value)
        @param r - index of A (last value)
        '''
        n1 = q - p + 1
        n2 = r - q
        L = [0 for k in range(n1+1)]
        R = [0 for k in range(n2+1)]

        for k in range(n1):
            L[k] = A[p + k]

        for k in range(n2):
            R[k] = A[q + k + 1]

        L[n1] = R[n2] = sys.maxint
        i = j = 0

        for k in range(p, r + 1):
            if L[i] <= R[j]:
                A[k] = L[i]
                i += 1
            else:
                A[k] = R[j]
                j += 1
        self.A = A
        pass

    
    def merge_sortSecundary(self, A, p, r):
        '''
        function merge_sortSecundary
        Merge Sort Algorithm
        Called every times less in the first
        Orders the elements in the sub sequences and calls merge function to unifies them
        @param A - list of numbers
        @param p - index of A (first value)
        @param r - index of A (last value)
        '''
        if p < r:
            q = int(math.floor((p + r) / 2))
            self.merge_sortSecundary(A, p, q)
            self.merge_sortSecundary(A, q + 1, r)
            self.merge(A, p, q, r)
            pass
        pass

    def merge_sort(self):
        '''
        function merge_sort
        Merge Sort Algorithm
        It's called once, in the first time, because has no parameters, to operate easily like librarie
        Then calls merge_sortSecundary passing the paremeters needed
        Orders the elements in the sub sequences and calls merge function to unifies them
        '''
        if self.p < self.r:
            q = int(math.floor((self.p + self.r) / 2))
            self.merge_sortSecundary(self.A, self.p, q)
            self.merge_sortSecundary(self.A, q + 1, self.r)
            self.merge(self.A, self.p, q, self.r)
            pass
        pass


